package com.wc.alorithm_blue_bridge._数学知识.质数.找素数;

/**
 * @Author congge
 * @Date 2025/3/17 19:36
 * @description
 * https://www.lanqiao.cn/courses/46292/learning/?id=3441393&compatibility=false
 */
public class Main {
    /**
     * 思路:
     * 欧拉筛/线性筛
     */
    static int N = 2000010;
    static boolean[] st = new boolean[N];
    static int[] prime = new int[N];
    static int cnt = 1;

    public static void main(String[] args) {
        ola(N - 1);
        System.out.println(prime[100002]);
    }

    static void ola(int n) {
        st[0] = st[1] = true;
        for (int i = 2; i <= n; i++) {
            if (!st[i]) prime[cnt++] = i;
            for (int j = 1; prime[j] <= n / i ; j++) {
                st[prime[j] * i] = true;
                if (prime[j] % i == 0) break;
            }
        }
    }
}


